Abstract State Machines (ASMs) have been used to simulate computer programs. See Gurevich, Y., Sequential Abstract State Machines Capture Sequential Algorithms, Microsoft Research, MSR-TR-99-65, revised Feb. 20, 2000. Further, modeling a complex real-world problem using a multi-agent system with an executable specification has been proposed. See Martelli, M., et al., Applying Logic Programming to the Specification of Complex Applications, 1997. Additionally, a communication protocol language has been proposed for sending information between communicating agents. Id.
Although agents communicating through a communication channel has been proposed, there is no discussion of sending and receiving messages between a set of abstract state machines representing a distributed application, through a set of abstract state machines representing the complex topology of a network. None of the present systems propose for example, an abstract state machine network model that can be used to model lost messages or creation of hosts and subnets in a network topology. Nor for example, does any proposed system observe the effects of host and or subnet failures in a dynamic complex network environment, or how modifications in host or subnet behaviors effect a complex network environment.
Inefficiencies in a network design are often not discovered until testing an implementation of that design. Since implementing a network design is resource intensive, waiting until a design is implemented before discovering potential design flaws can be very expensive. Further, modifications made to an existing network implementation can create inefficiencies and other side effects that also remain latent until the modification is implemented. A model for observing how messages travel from plural hosts executing distributed applications through a proposed network topology, would be very valuable. Thus, it would be desirable to test a proposed network design or network modification before implementation.
The following embodiments explore algorithms for modeling aggregate network behaviors with plural interrelating abstract state machines representing the topology of a network. An executable specification for a network design in an abstract state machine language is created, thereby allowing an arbitrary design to be tested before implementation. In this regard, a generic algorithm, based on plural executing ASMs is discussed for simulating communications software in a network environment. The dynamic properties are determined through adjustable parameters of the generic algorithm such as network topology, delaying behaviors, and message transport protocol reliability. The discussion focuses first on a set of generalized agents including delivery agents and endpoint agents necessary for modeling a generic and dynamic network. To this minimum set, potential parameters necessary to model specific network behaviors are considered.
Such a network model can be used to model lost messages, creation and registration of hosts and subnets to the network topology, and consequences of host and or subnet failure. Further, the effects of changes in host behavior on the network can be modeled and observed.
In one aspect, plural agents, each a sequential abstract state machine, are combined to simulate the behavior of a network environment. The environment may be distributed. The agents send and receive messages on the model network. Message frequency, size, packet protocol, and other parameters are added and varied to test various behavioral aspects. Messages are broadcast, multi-cast, or point-to-point. Agent and message behavior is altered based on the proposed or selected network under simulation. The desired behaviors and constraints are coded, compiled, and executed using an executable abstract state machine language.
In another aspect, delivery agents are constrained to act as intermediaries to accept messages from and forward messages to other agents. Each of those other agents (or recipients) is again either a delivery agent or an endpoint agent.
In another aspect, endpoint agents and delivery agents are constrained to simulate network protocol specific behaviors, networks communicating with networks, or agents communicating with agents.
Thus, a generic adaptable algorithm as embodied in plural executing abstract state machine is now available to simulate network behavior. It can be used to simulate a combination of networks with dynamic and random behaviors. At the level of abstraction available with this generic algorithm as embodied in an abstract state machine, designers can alter the proposed design, play with varied scenarios, add and test proposed features, introduce random behavior, and generate test suites in order to determine how the proposed network responds.
Additional features and advantages will be made apparent from the following detailed description of the illustrated embodiment which proceeds with reference to the accompanying drawings.